package easy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution_LCP_40 {
    public int maxmiumScore(int[] cards, int cnt) {
        int[] counts = new int[1001];
        for (int card : cards) {
            counts[card]++;
        }
        List<Integer> list_1 = new ArrayList<>();
        List<Integer> list_2 = new ArrayList<>();
        for (int i = 0; i < counts.length; i++) {
            if (counts[i]>0) {
                for (int j = 0; j < counts[i]; j++) {
                    if (i % 2 == 0) {
                        list_2.add(i);
                    } else {
                        list_1.add(i);
                    }
                }
            }
        }
        /*for (int card : cards) {
            if (card % 2 == 0) {
                list_2.add(card);
            } else {
                list_1.add(card);
            }
        }
        Collections.sort(list_1);
        Collections.sort(list_2);*/
        int max_1 = Math.min(cnt / 2, list_1.size() / 2);
        int min_1;
        if (list_2.size() >= cnt) {
            min_1 = 0;
        } else {
            min_1 = (cnt - list_2.size() + 1) / 2;
        }
        if (min_1 > max_1) {
            return 0;
        }

        int pre_sum_2 = 0;
        int index_2 = list_2.size();
        for (int i = 1; i <= (cnt - min_1 * 2); i++) {
            index_2--;
            pre_sum_2 += list_2.get(index_2);
        }

        int pre_sum_1 = 0;
        int index_1 = list_1.size();
        for (int i = 1; i <= min_1 * 2; i++) {
            index_1--;
            pre_sum_1 += list_1.get(index_1);
        }

        int pre = pre_sum_1 + pre_sum_2;
        int res = pre;
        for (int i = min_1 + 1; i <= max_1; i++) {
            int num = pre - list_2.get(index_2++) - list_2.get(index_2++) + list_1.get(--index_1) + list_1.get(--index_1);
            res = Math.max(res, num);
            pre = num;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution_LCP_40 model = new Solution_LCP_40();
        System.out.println(model.maxmiumScore(new int[]{1, 2, 8, 9}, 3)); // 18
        System.out.println(model.maxmiumScore(new int[]{3, 3, 1}, 1)); // 0
        System.out.println(model.maxmiumScore(new int[]{1, 10, 5, 2, 9}, 4)); // 26
        System.out.println(model.maxmiumScore(new int[]{3, 1, 6, 9, 2, 4, 9, 2, 3}, 4)); // 26
    }
}
